﻿namespace Leetcode.N0403;

public class Solution
{
    public bool CanCross(int[] stones)
    {
        var steps = new System.Collections.Generic.HashSet<int>[stones.Length];
        steps[0] = new System.Collections.Generic.HashSet<int>();
        steps[0].Add(1);
        for (var i = 0; i < stones.Length; i++)
        {
            if (this.CanCross(stones, i, steps))
            {
                return true;
            }
        }
        return false;
    }

    private bool CanCross(int[] stones, int index, System.Collections.Generic.HashSet<int>[] steps)
    {
        if (steps[index] == null)
        {
            return false;
        }
        foreach (var step in steps[index])
        {
            var v = stones[index] + step;
            for (var j = index + 1; j < stones.Length; j++)
            {
                if (stones[j] > v)
                {
                    break;
                }

                if (stones[j] == v)
                {
                    if (j == stones.Length - 1)
                    {
                        return true;
                    }
                    if (steps[j] == null)
                    {
                        steps[j] = new System.Collections.Generic.HashSet<int>();
                    }
                    if (step >= 1)
                    {
                        steps[j].Add(step - 1);
                    }
                    steps[j].Add(step);
                    steps[j].Add(step + 1);
                    break;
                }
            }
        }
        return false;
    }

}
